//
// Created by yanhai on 2021/1/17.
//

#include <iostream>
#include "graph.h"

using namespace std;

int main()
{
    CGraph graph(false);  // 无向图

    // 顶点集合
    vector<VexType> vex = {"A", "B", "C", "D", "E", "F"};
    // 边集合
    vector<GArc> arc = {
            {"A", "B"},
            {"A", "C"},
            {"A", "D"},
            {"B", "C"},
            {"B", "F"},
            {"C", "E"},
            {"E", "F"},
            {"E", "D"},
    };
    // 和边一一对应的权重集合
    vector<int> weights = {
            7,
            9,
            11,
            8,
            20,
            6,
            1,
            3,
    };

    // 根据 顶点 边 权重 创建一个图
    graph.CreateGraph(vex, arc, weights);

    // 修改 <'A', 'B'> 的权，请对比修改前后的 Dijkstra
//    graph.UpdateArcWeight(make_pair("A", "B"), 20);

    auto vex_print_func = [](const GVex &vex) {
        cout << vex.data << " -> ";
        return true;
    };

    // 深度优先遍历
    {
        cout << "DFS: " << endl;
        graph.DFSTraverse(vex_print_func);
        cout << "NULL" << endl;
    }

    // 广度优先遍历
    {
        cout << "BFS: " << endl;
        graph.BFSTraverse(vex_print_func);
        cout << "NULL" << endl;
    }

    // 迪杰斯特拉 最短路径问题
    {
        vector<bool> visited(graph.VexSize(), false);
        vector<WeightType> dis(graph.VexSize(), INF);
        vector<int> parent(graph.VexSize(), -1);

        graph.Dijkstra("A", visited, dis, parent);

        cout << "Dijkstra: " << endl;
        for (int i = 0; i < parent.size(); ++i) {
            cout << vex[i] << " -> " << (visited[i] ? "true" : "false")
                 << " -> " << dis[i]
                 << " -> " << vex[parent[i]] << endl;
        }
    }

    // 迪杰斯特拉 最短路径问题
    {
        auto r = graph.Dijkstra("A");

        cout << "Dijkstra2: " << endl;
        for (int i = 0; i < r.size(); ++i) {
            cout << vex[i]
                 << " -> " << r[i].first
                 << " -> " << vex[r[i].second] << endl;
        }
    }

    // 'A' -> 'E' 最短路径
    {
        auto r = graph.VexPathMin("A", "E");
        cout << "VexPathMin: " << endl;
        for (auto &item: r) {
            cout << item << " -> ";
        }
        cout << "end" << endl;
    }

    return 0;
}
